package ftd.edu.search;

/**
 * @Description: .
 * @Author: ZhaoWeiNan .
 * @CreatedTime: 2017/7/4 .
 * @Version: 1.0 .
 */
public class Search {


    public static int binarySearch(int[] array,Integer key){

        if (array == null || array.length < 1){
            //数组为空返回-1
            return -1;
        }

        int left = 0;
        int right = array.length - 1;
        int middle;
        int middleValue;
        while (left <= right) {
            //>>>这个运算符大致讲一下，
            //是无符号右移运算符，是把二进制的数，向右移动一位
            //比如说  4 对应的二进制是： 100  右移一位是 10 转换成十进制是 2
            //比如说  5 对应的二进制是： 101  右移一位是 10 转换成十进制是 2
            //>>>1 就是相当于java中做了除以2的计算
            //算出中间的下标
            middle = (left + right) >>> 1;
            //取出中间的元素
            middleValue = array[middle];

            //如果大于中间元素在右边里面找
            if (middleValue < key)
                left = middle + 1;
            //如果小于中间元素在左边里面找
            else if (middleValue > key)
                right = middle - 1;
            //等于就找到了
            else
                return middle;
        }
        //没找到返回-1
        return -1;

    }

    /**
     * 查找第一个大于key的元素下标
     * @param array
     * @param key
     * @return
     */
    public static int binarySearchMax(int[] array,Integer key){

        if (array == null || array.length < 1){
            //数组为空返回-1
            return -1;
        }

        int left = 0;
        int right = array.length - 1;
        int middle;
        int middleValue;
        while (left <= right) {

            middle = (left + right) >>> 1;
            //取出中间的元素
            middleValue = array[middle];

            //因为要找出小于key的最后一个元素的下标，所以对这边的逻辑改造了一下
            //如果大于等于中间元素在右边里面找
            if (middleValue <= key)
                left = middle + 1;
            //如果小于中间元素在左边里面找
            else
                right = middle - 1;
        }
        //返回右面的,就是小于key的最后一个元素的下标
        return left;

    }

    /**
     * 查找最后一个小于key的元素下标
     * @param array
     * @param key
     * @return
     */
    public static int binarySearchMin(int[] array,Integer key){

        if (array == null || array.length < 1){
            //数组为空返回-1
            return -1;
        }

        int left = 0;
        int right = array.length - 1;
        int middle;
        int middleValue;
        while (left <= right) {

            middle = (left + right) >>> 1;
            //取出中间的元素
            middleValue = array[middle];

            //因为要找出小于key的最后一个元素的下标，所以对这边的逻辑改造了一下
            //如果key小于等于中间元素在左边数组里面找
            if (middleValue >= key)
                right = middle - 1;
            //反之在右边数组找
            else
                left = middle + 1;
        }
        //返回右面的,就是小于key的最后一个元素的下标
        return right;

    }

    public static void main(String[] args){
        int[] array = new int[]{1,3,5,6,7,8,9,10,11};
        int[] array1 = new int[]{1,1,1,1,1,3,3,3,3,3,3,5,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,9,9,10,10,10,11,11,11,11};
        System.out.println(binarySearch(array,5));
        System.out.println(binarySearchMin(array1,5));
        System.out.println(binarySearchMax(array1,5));

    }
}
